import javax.swing.tree.TreeNode;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/22 21:05
 */
// 二叉树的最近公共祖先
    //递归解法和dfs解法
public class Solution236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 先看节点是不是祖先
        if (root == null || root == p || root == q) {
            return root;
        }

        // 后序遍历
        // 找左子树
        TreeNode left = lowestCommonAncestor(root.left, p ,q);
        // 找右子树
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null && right == null) {
            return null;
        }else if (left == null && right != null) {
            return right;
        }else if (left != null && right == null) {
            return left;
            // 若找到了两个节点
        }else {
            // 如果没有更近的，还是默认返回root
            return root;
        }
    }
}
